package datastruct;

import org.junit.Test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class MaxSlidingWindow239 {

    @Test
    public void test() {
        maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        maxSlidingWindow(new int[]{1,3,1,2,0,5}, 3);
        maxSlidingWindow(new int[]{-7,-8,7,5,7,1,6,0}, 4);
    }

    // 使用单调队列, 以单调减小的形式保存最近k个元素中.
    // 基于这样的认知: 如果某个元素nums[i]在某个窗口中是最大的, 那么在后面包含num[i]的所有窗口中, 下标比i小的元素绝对不可能是最大的, 因为他们都比num[i]小啊.
    // 三部曲: pushWithEatingSmaller, getMax(), removeFirstIfEqual()

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] max = new int[nums.length-k+1];
        Deque<Integer> q = new LinkedList<>();
        int i = 0;
        for (i = 0; i < k-1; i++) {
            addLastWithEatingSmaller(q, nums, i);
        }
        for ( ; i < nums.length; i++) {
            addLastWithEatingSmaller(q, nums, i);
            max[i-k+1] = nums[q.getFirst()];
            removeFirstIfEqual(q, i-k+1);
        }
        System.out.format("k: %d, nums: %s, max: %s\n", k, Arrays.toString(nums), Arrays.toString(max));
        return max;
    }

    public void addLastWithEatingSmaller(Deque<Integer> q, int[] nums, int i) {
        while (q.size() > 0 && nums[q.getLast()] <= nums[i]) {
            q.removeLast();
        }
        q.addLast(i);
    }

    // 根据下标而不是根据值来删除元素
    public void removeFirstIfEqual(Deque<Integer> q, int i) {
        if (q.getFirst() == i) {
            q.removeFirst();
        }
    }

    /* 注意: queue中要存下标, 不能存数值, removeFirstIfEqual可能删错元素
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] max = new int[nums.length-k+1];
        Deque<Integer> q = new LinkedList<>();
        int i = 0;
        for (i = 0; i < k-1; i++) {
            addLastWithEatingSmaller(q, nums[i]);
        }
        for ( ; i < nums.length; i++) {
            addLastWithEatingSmaller(q, nums[i]);
            max[i-k+1] = q.getFirst();
            removeFirstIfEqual(q, nums[i-k+1]);
        }
        System.out.format("k: %d, nums: %s, max: %s", k, Arrays.toString(nums), Arrays.toString(max));
        return max;
    }

    public void addLastWithEatingSmaller(Deque<Integer> q, int n) {
        while (q.size() > 0 && q.getLast() <= n) {
            q.removeLast();
        }
        q.addLast(n);
    }

    // 这里有问题, 可能把不是对应index的元素删掉了
    public void removeFirstIfEqual(Deque<Integer> q, int n) {
        if (q.getFirst() == n) {
            q.removeFirst();
        }
    }
    */
}
